Overleg:Zeef van Eratosthenes

De efficiency in een computer zit hem erin dat je de getallen AANstreept, niet WEGhaalt. Als je bij elk getal moet controleren of het deelbaar is, is dat niet efficient. Het wordt pas snel als je gewoon voor "3" elk derde getal kunt aanstrepen zonder de deling uit te voeren! Rob Hooft 30 mrt 2003 12:03 (CEST)

een semantische kwestie, ik bedoel dat je een vlag zet dat dit getal niet meer meedoet, niet dat het array wordt gecomprimeerd uiteraard. Evanherk 30 mrt 2003 12:35 (CEST)

Hm, vreemd dat dit nooit eerder is opgepakt. Zoals het er nu staat is het inderdaad uitermate onhandig: men moet alsnog steeds voor getallen bepalen of ze veelvouden zijn. Volgens mij is dit ook niet de algoritme die algemeen bekend staat als de Zeef van Eratosthenes, het idee was volgens mij inderdaad juist dat je gedachteloos ieder n-de getal uit de lijst kon strepen. Paul B 19 jan 2009 03:16 (CET)

Bovenstaande opmerkingen uit 2003 slaan ongetwijfeld op de toenmalige versie van dit artikel. De huidige versie van het artikel lijkt mij in orde. Mocht je iets 'onhandigs' menen te zien, geef dan even aan op welke passage je precies doelt, want dat is me nu nog niet duidelijk. Bob.v.R 19 jan 2009 03:30 (CET)

De passages waar wordt gezegd: "streep nu alle veelvouden van ... weg". Daarvoor moet je nl. alsnog gaan bepalen voor ieder getal of het een veelvoud van ... is. Dat is niet handig. Vooral in de sectie "voorbeeld", waar de getallen ook fysiek worden weggehaald. Paul B 19 jan 2009 03:35 (CET)

Dank voor je reactie. Betreffende 'bepalen' of een getal een veelvoud is 'van': nou, de complexiteit daarvan valt nogal mee. Wat er gebeurt is dat wordt begonnen bij een gevonden priemgetal, en vervolgens wordt dat vrij 'mechanisch' vermenigvuldigd met 2, 3, etc. en de verkregen getallen zijn vanzelfsprekend de veelvouden. Het is dus niet zo dat we een getal pakken en kijken of dat een veelvoud is. Nee, iedere keer nadat er een priemgetal gevonden is, worden de veelvouden volgens een kort en 'automatisch' algoritme bepaald: het vermenigvuldigen van het priemgetal met een geheel getal. Superhandig toch? Bob.v.R 19 jan 2009 03:53 (CET)

Ik ben er niet van overtuigd. Ook het opzoeken van een getal in een lijst (want dat is dan nodig) is lastiger dan gewoon het rijtje af en getallen wegstrepen. Het is wel handiger danwat ik eerst suggereerde, dat is duidelijk. Paul B 19 jan 2009 03:58 (CET) P.S.: wat het algoritme dus niet specificeert, is wat met "wegstrepen" wordt bedoeld, en hoe je die veelvouden bepaalt. De methode onder "voorbeeld" is hopeloos gecompliceerd in ieder geval. Paul B 19 jan 2009 04:00 (CET)

Computerprogramma?

Ik twijfel of we een computerprogramma nodig hebben, maar als dat zo is, kunnen we dan een correcte, en ANSI-C versie nemen? Ik zou zeggen:

#include <stdio.h>
#include <stdlib.h>

int main( int argc, char **argv){
   unsigned maxpriem, i, j;
   char *priemen;

   /* Voorbereiding */
   if (argc != 2)
      return EXIT_FAILURE;
   maxpriem= atoll( argv[ 1]);
   priemen= (char *)calloc( maxpriem +1, 1);
  
   /* Zeef: */
   for (i= 2; i*i <= maxpriem; i++)
      if( priemen[ i] == 0)
         for (j= 2*i; j <= maxpriem; j += i)
            priemen[ j]= 1;

   /* Afdrukken: */
   for (i= 2; i <= maxpriem; i++)
      if (priemen[ i] == 0)
         printf("%u ",i);
   putchar('\n');

   return EXIT_SUCCESS;
}

maar daar zal wel weer een of andere codeerfout in zitten. Aliter 13 nov 2004 19:30 (CET)

ik zou ook een minimumgetal instellen om van af te beginnen, bijvoorbeeld het grootst bekende priemgetal. Door minimumgetal door i te delen weet je vanaf waar je de j moet laten lopen. Arakrys 213.84.114.40

Voorbeeld

Het is bijna niet te zien dat bij het voorbeeld de 4 doorgestreept is, misschien is een ander kleurtje geven beter? 83.117.99.48 18 feb 2008 18:24 (CET)

betrouwbaarheid van de zeef

Als je een getal door 2, 3, 5 en 7 kan delen, is het dus geen priemgetal, en als je het niet door die 4 getallen kan delen, is het automatisch wel een priemgetal. Dit klopt zeker bij relatief kleine getallen, maar als je in de miljoenen / miljarden of hoger zit, klopt het dan nog steeds?

kan iemand mij een priemgetal noemen dat niet deelbaar door deze 4 getallen is maar toch geen priemgetal is? (getallen onder de 7 niet meegeteld natuurlijk) - – De voorgaande bijdrage werd geplaatst door 212.83.84.207 (overleg · bijdragen)

13 * 13, bijboorbeeld 80.101.55.174 19 jan 2009 02:12 (CET)

De zeef is 100% betrouwbaar, maar je moet het wel doen zoals het er staat. Bob.v.R 19 jan 2009 02:16 (CET)

(hm, Bob.v.R. was mij voor maar ik zet het toch nog maar even neer) Ja, maar hier wordt een denkfout gemaakt. De zeef stopt niet bij 7 of 9. Je stopt pas als je zeker weet dat er geen niet-priemgetallen meer over zijn in het bereik dat je beschouwt. Als je tot de 10.000 gaat, houd je pas op nadat je alle veelvouden van 97 hebt weggestreept (het volgende veelvoud dat je zou moeten wegstrepen is nl. 101, en dat is groter dan 100, de wortel uit 10.000). De zeef is 100% betrouwbaar als je hem goed toepast. Het is overigens een zeer inefficiente manier om priemgetallen te vinden, maar dat is een andere kwestie. Paul B 19 jan 2009 02:24 (CET)

Precies, kennelijk zijn er sommigen door de fraaie animatie op het verkeerde been gezet. Algemeen geldt: als je de priemgetallen onder de N wilt uitzeven, dan moet je veelvouden nemen van alle priemgetallen vanaf 2 tot de wortel uit N. Bob.v.R 19 jan 2009 02:35 (CET)

Snellere code VB

Deze code doorloop het 2de gedeelte veel minder vaak.
Bij ZoekenTotGetal 100 is de huidige tot 9801x, deze 171x.
Het kan zijn dat er nog Visual Basic .NET code in zit, maar als goed is moet het zo werken.

programmeertaal Visual Basic

   Private Sub Form_Load()
       Const ZoekenTotGetal = 100                          '** Of tot welke waarde dan ook **
       Dim filter(ZoekenTotGetal) As Boolean                             'alle getalleen tot ZoekenTotGetal

       For I = 2 To ZoekenTotGetal
           If filter(I) = False Then                                       'als getal niet uitgefilterd is
               Print I                                                       'dan is het priem
               For J = I To ZoekenTotGetal Step I                            'en filter je alle getallen met priemfactor eruit
                 filter(J) = True
               Next
           End If
       Next
   End Sub

– De voorgaande bijdrage werd geplaatst door 82.171.8.216 (overleg · bijdragen)

Zie een kleine fout in de code, had ZoekenTotGetal en de sub niet gedeclareerd

Grootste priemgetal?

De tekst suggereert dat er een grootste priemgetal is. Ik ben er al weer ruim 30 jaar uit, maar van de wiskundelessen meen ik me te herinneren dat dit niet het geval is of bedoelt men iets anders?
Flederlander 6 aug 2010 13:08 (CEST)

Er bestaat inderdaad geen grootste priemgetal, maar waar haal jij die suggestie uit de tekst vandaan? Ik kan geen tekst vinden waaruit blijkt dat gesuggereerd wordt dat er een grootste priemgetal zou zijn. Groeten, Look Sharp! 6 aug 2010 13:11 (CEST)

In regel 1 staat niet alleen dat er een maximum is, maar zelfs dat het al bepaald is: Kun je dan niet beter spreken van gekozen, maximum naar keuze of iets dergelijks? Ik zeg maar wat met mijn boerenverstand 8-) Flederlander 6 aug 2010 13:24 (CEST)

Ik heb er zelf te kiezen van gemaakt, i.p.v, bepaald. Overigens neem ik aan dat de oorspronkelijke maker van deze tekst dit ook zo bedoeld heeft en zeker niet dat er een maximum priemgetal zou zijn, het is slechts het maximum in het eigen lijstje. Look Sharp! 6 aug 2010 14:52 (CEST)

Dank je, Look Sharp! Je doet je naam eer aan. Je ziet het scherper en bovenal is het nu logischer verwoord dan de oorspronkelijke auteur deed 8-) Flederlander 6 aug 2010 23:33 (CEST)